'''
Module: ep_core.py
Purpose: Implements the Earley parsing logic.
Author: Avishay Alon
'''
#########################################
### Imports
#########################################
from collections import defaultdict
from ep_grammar import Rule
from time import time

#########################################
### Classes
#########################################
class DottedRule(object):
    ''' The DottedRule object contains a Rule object and a dot index property. '''
    NEXT_ID = 0
    def __init__(self, rule, dot_index, i=None, j=None, children=None):
        self._rule = rule
        self._dot_index = dot_index
        self._is_active = dot_index < len(rule)
        self._time_added = time()
        self._id = DottedRule.NEXT_ID
        DottedRule.NEXT_ID += 1
        self.i = i
        self.j = j
        if not children:
            children = set()
        self.children = children
        
    def next_term(self):
        ''' Return the term/symbol following the dot index. '''
        return self._rule.production.split()[self._dot_index]

    def __str__(self):
        return '%s, dot = %d, [%d, %d], id=%d' % (self._rule, self._dot_index, self.i, self.j, self._id, )

    def __eq__(self, other):
        return (self._rule == other.rule and 
                    self._dot_index == other.dot_index and
                    self.i == other.i and
                    self.j == other.j)
    def __ne__(self, other):
        return not (self == other)

    production = property(lambda self: self._rule.production)
    active = property(lambda self: self._is_active)
    rule = property(lambda self: self._rule)
    dot_index = property(lambda self: self._dot_index)

class EarleyParser(object):
    ''' This class contains all the logic of the Earley parsing algorithm. 
        Assumes the grammar given is of class Grammar. '''
    def __init__(self, grammar):
        ''' Initialization method. must provide grammar. '''
        self._chart = None
        self._grammar = grammar
        self._outputs = []
        self._transitions = defaultdict(list)
        self._pairs = []

    def _get_all_edges(self):
        ''' Scans the chart and returns all the existing edges. '''
        edges = set()
        for i in self._chart.keys():
            for j in self._chart.keys():
                for edge in self._chart[i][j]:
                    edges.add(edge)
        return edges

    def _get_rightsisters(self, edge):
        ''' Given an active edge A -> x*By, 
            create and return edges for rules B -> *z '''
        if not edge.active or edge.rule.is_terminal:
            return []
        term = edge.next_term()
        if term not in self._grammar.nonterminals:
            return []
        return [ DottedRule(rule, 0) for rule in self._grammar.rule_set if rule.head == term ]

    def _get_leftsisters(self, edge):
        ''' Given an inactive/complete edge B -> z*, 
            return all existing edges A -> x*By '''
        if edge.active:
            return []
        return [ leftsister for leftsister in self._get_all_edges()
                    if leftsister.active and
                    leftsister.next_term() == edge.rule.head ]

    def _enteredge(self, i, edge, j):
        ''' Recursively perform predictions and completions on edges. '''
        if edge in self._chart[i][j]:
            return
        self._chart[i][j].append(edge)
        ## Predict
        if edge.active:
            for rightsister in self._get_rightsisters(edge):
                self._enteredge(j, rightsister, j)
        ## Complete
        else:
            for leftsister in self._get_leftsisters(edge):
                for k in [ index for index in self._chart.keys() 
                            if leftsister in self._chart[index][i] ]:
                    combined = DottedRule(leftsister.rule, leftsister.dot_index + 1, i=k, j=j, children=set([edge]))
                    self._transitions[repr(combined.rule)].append(repr(edge.rule))
                    
                    if Pair(combined.rule, edge.rule, i=i, k=k, j=j) not in self._pairs:
                        self._pairs.append(Pair(combined.rule, edge.rule, i=i, k=k, j=j))
                    
                    if str(combined.rule) not in self._outputs and str(edge.rule) not in self._outputs:
                        self._outputs.append((str(combined.rule)))
                        self._outputs.append((str(edge.rule)))
                    # print combined.rule, edge.rule
                    self._enteredge(k, combined, j)

    def _init_chart(self, length):
        ''' Initialize the chart: chart[i][j] = list of edges. '''
        self._chart = {}
        for index in range(length + 1):
            self._chart[index] = defaultdict(list)

    def parse(self, words):
        ''' The parse method returns True if the input given is parsable 
            from the grammar given, and False otherwise. '''
        self._init_chart(len(words))
        ## Add the start rule
        start_rule = Rule("S'", self._grammar.start_symbol)
        self._enteredge(0, DottedRule(start_rule, 0, i=0, j=0), 0)
        ## Scan the input words
        for j in range(len(words)):
            for rule in self._grammar.terminal_rules:
                if words[j] == rule.production:
                    self._enteredge(j, DottedRule(rule, 1, i=j, j=j+1), j + 1)
        ## Is the final edge found in [0][n]?
        derivation_rules = defaultdict(set)
        nodes = []
        all_edges = [edge for edge in self._get_all_edges()]
        for edge in [edge for edge in all_edges]:
            derivation_rules[edge.rule] = derivation_rules[edge.rule].union(edge.children)
        
        # for i in self._chart.keys():
            # for j in self._chart.keys():
                # for edge in self._chart[i][j]:
                    # if edge.rule.head == 'VP' and edge.rule.production == 'V NP':
                        # for child in edge.children:
                            # print '  >', child
                            
        for element in self._chart[0][len(words)]:
            if DottedRule(start_rule, 1) == element:
                # print 'Found final edge. Constructing tree.'
                roots = self.make_forest(element)
                break
        
        for pair in self._pairs:
            print pair
            
        print '--------------------------------'
        bfs_q = [pair for pair in self._pairs if pair.father.head == "S'" and pair.j == len(words)]
        if len(bfs_q) != 1:
            raise ValueError(starts)
        level = 0
        childrens = {}
        while bfs_q:
            current = bfs_q.pop()
            
            next = [pair for pair in self._pairs if current.child == pair.father]
            q = []
            for n in next:
                valid = False
                if len(current.child) == 1:
                    if (n.k, n.j) == (current.i, current.j):
                        q.append([n])
                        bfs_q.append(n)
                        valid = True
                else:
                    for aux in next:
                        if ((current.i, current.j) == (n.i, aux.j) and n.j == aux.i):
                            q.append([n, aux])
                            bfs_q.append(aux)
                            bfs_q.append(n)
                            valid = True
                        if ((current.i, current.j) == (aux.i, n.j) and aux.j == n.i):
                            q.append([aux, n])
                            bfs_q.append(n)
                            bfs_q.append(aux)
                            valid = True
                if valid:
                    print ' ' * len(bfs_q) + 'Cur:', current.child
                    print ' ' * len(bfs_q) + '*', n.child
            
            childrens[level] = q
            print '< Finished level %d, bfs_q: %d, new subtrees: %d >' % (level, len(bfs_q), len(q), )
            level += 1
        print '--------------------------------------------'
        
        return DottedRule(start_rule, 1) in self._chart[0][len(words)], self._outputs
        
    def make_forest(self, start_rule):
        return self.make_forest_aux([], start_rule)

    def make_forest_aux(self, children, start_rule):
        pass
        
def print_dict(dicti, current_key, level = 0):
    print "  " * level + str(current_key)
    if current_key not in dicti:
        return
    for child in dicti[current_key]:
        print_dict(dicti, child, level + 1)

class Pair(object):
    def __init__(self, father, child, i=None, k=None, j=None):
        self.father = father
        self.child = child
        self.i = i
        self.k = k
        self.j = j
        
    def __str__(self):
        return 'F: %s [%d,%d] | C: %s [%d,%d]' % (self.father, self.k, self.j, self.child, self.i, self.j, )
        
    def __eq__(self, other):
        return (self.father == other.father and 
                    self.child == other.child and
                    self.i == other.i and
                    self.j == other.j and
                    self.k == other.k)
        
class Node(object):
    def __init__(self, value, children):
        self.value = value
        self.children = children

    def print_(self, level = 0):
        print " " * level + str(self.value)
        for child in self.children:
            child.print_(level + 1)
            
    def get(self, value):
        if self.value == value:
            return self
        else:
            for child in self.children:
                return child.get(value)
